/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-06-22
 * Time: 23:05
 */
//实现双线不带头不循环链表
public class MyLinkedList {
    public int val;
    public MyLinkedList next;
    public MyLinkedList prev;
    public MyLinkedList head;
    public MyLinkedList last;
    public MyLinkedList () {
    }
    public MyLinkedList(int data){
        this.val=data;
    }
    //头插法
    public void addFirst(int data){
        MyLinkedList node=new MyLinkedList(data);
        if(head==null){
            head=node;
            last=node;
            return ;
        }
        node.next=head;
        head.prev=node;
        head=node;
    }
    //尾插法
    public void addLast(int data){
        MyLinkedList node=new MyLinkedList(data);
        if(head==null){
            head=node;
            last=node;
            return ;
        }
        node.prev=last;
        last.next=node;
        last=node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("无效的位置，插入失败");
            return false;
        }
        if(index==0){
            addFirst(data);
            return true;
        }
        if(index==size()){
            addLast(data);
            return true;
        }
        MyLinkedList node=new MyLinkedList(data);
        MyLinkedList p=head;
        while(index>0){
            index--;
            p=p.next;
        }
        node.next=p;
        node.prev=p.prev;
        node.prev.next=node;
        node.next.prev=node;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(head==null){
            return false;
        }
        MyLinkedList p=head;
        while(p!=null){
            if(p.val==key){
                return true;
            }
            p=p.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head==null){
            return ;
        }
        MyLinkedList p=head;
        int size=size();
        int n=0;
        while(p!=null){
            if(p.val==key){
                if(n==0){
                    if(p.next==null){
                        head=null;
                    }
                    else{
                    head.next.prev=null;
                    head=head.next;
                    }
                    return ;
                }
                if(n==size-1){
                    last.prev.next=null;
                    last=last.prev;
                    return ;
                }
                p.next.prev=p.prev;
                p.prev.next=p.next;
                return ;
            }
            p=p.next;
            n++;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head==null){
            return ;
        }
        MyLinkedList p=head;
        int size=size();
        int n=0;
        while(p!=null){
            if(p.val==key) {
                if (n == 0) {
                    if(p.next==null){
                        head=null;
                    }
                    else{
                    head.next.prev = null;
                    head = head.next;
                    }
                } else if (n == size - 1) {
                    last.prev.next = null;
                    last = last.prev;
                } else {
                    p.next.prev = p.prev;
                    p.prev.next = p.next;
                }
            }
            p=p.next;
            n++;
        }
    }
    //得到单链表的长度
    public int size(){
        if(head==null){
            return 0;
        }
        int n=0;
        MyLinkedList p=head;
        while(p!=null){
            n++;
            p=p.next;
        }
        return n;
    }
    public void display(){
        MyLinkedList p=head;
        System.out.print("[ ");
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.next;
        }
        System.out.print("]");
        System.out.println("");
    }
    public void clear(){
        if(head==null){
            return;
        }
        MyLinkedList p1=head;
        MyLinkedList p2=head.next;
        while(p2!=null){
            p1.prev=null;
            p1.next=null;
            p1=p2;
            p2=p2.next;
        }
        head=null;
        last=null;
    }

}
